package com.datastructure.test.widthofbinarytree;

import java.util.ArrayList;

public class WidthOfBinaryTree {

    public static void main(String[] args) {
        WidthOfBinaryTree widthOfBinaryTree = new WidthOfBinaryTree();
        TreeNode root = new TreeNode(1);
        root.left=new TreeNode(2);
        root.left.left=new TreeNode(4);
        root.left.left.left=new TreeNode(6);
        root.right=new TreeNode(3);
        root.right.left=new TreeNode(4);
        root.right.right=new TreeNode(5);
        root.right.left.left=new TreeNode(1);
        int width = widthOfBinaryTree.widthOfBinaryTree(root);
        System.out.println(width);
    }

    int temp = Integer.MAX_VALUE;
    int depth =0;
    public int widthOfBinaryTree (TreeNode root) {
        // write code here
        int maxWide=0;
        depth = maxDepth(root);
        fillTree(root,1);
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        levelOfIteratorTree(root,res,0);
        for (ArrayList<Integer> list : res) {
            int length = list.size();
            for (Integer integer : list) {
                if (integer == Integer.MAX_VALUE) {
                    length--;
                } else {
                    break;
                }
            }
            for (int size = list.size()-1; size >= 0; size--) {
                if(list.get(size)==Integer.MAX_VALUE){
                    length--;
                } else {
                    break;
                }
            }
            maxWide=Math.max(maxWide,length);
        }
        return maxWide;
    }

    private void levelOfIteratorTree(TreeNode root, ArrayList<ArrayList<Integer>> res, int level) {
        if(level==res.size()){
            res.add(new ArrayList<>());
        }
        res.get(level).add(root.val);
        if(root.left!=null){
            levelOfIteratorTree(root.left,res,level+1);
        }
        if(root.right!=null){
            levelOfIteratorTree(root.right,res,level+1);
        }
    }

    private void fillTree(TreeNode root,int curDepth) {
        if(root==null){
            return;
        }
        if(root.right == null&&root.left == null&&curDepth<=depth){
            root.right=new TreeNode(temp);
            root.left=new TreeNode(temp);
        } else
        if(root.left == null&&curDepth<=depth){
            root.left=new TreeNode(temp);
        } else
        if(root.right == null&&curDepth<=depth){
            root.right=new TreeNode(temp);
        }
        fillTree(root.left,curDepth+1);
        fillTree(root.right,curDepth+1);

    }

    public int maxDepth (TreeNode root) {
        if(root == null){
            return 0;
        }
        int max = 0;
        if(root.left!=null){
            max = Math.max(max,maxDepth(root.left));
        }
        if(root.right!=null){
            max = Math.max(max,maxDepth(root.right));
        }
        return max+1;
    }
}

class TreeNode {
   int val = 0;
   TreeNode left = null;
   TreeNode right = null;
   public TreeNode(int val) {
     this.val = val;
   }
 }